package com.leet.grapth;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class IsBipartite {
    public boolean isBipartite(int[][] graph) {
        // q.offer和visited的赋值是绑定的，染完色再放进去
        int n = graph.length;
        int[] visited = new int[n];
        Arrays.fill(visited,0);
        for(int i = 0 ; i < n; i++){
            if(visited[i] == 0 && graph[i].length > 0){
                Queue<Integer> q = new LinkedList<>();
                q.offer(i);
                visited[i] = 1;
                while(!q.isEmpty()){
                    int size = q.size();
                    for (int j = 0; j < size; j++) {
                        Integer front = q.poll();
                        for(int next: graph[front]){
                            if(visited[next] == 0){
                                q.offer(next);
                                visited[next] = visited[front] * (-1);
                            }else if(visited[next] == visited[front]){
                                return false;
                            }
                        }
                    }
                }
            }
        }
        return true;
    }
}
